package offer.nowcoder.queue_stack;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 不会做
 * 按理说，可以想到插入排序的啊
 * @author DengYuan2
 * @create 2021-02-17 20:28
 */
public class n_41_1 {
    public static void main(String[] args) {
        double x = (2+3)/2.0;
        System.out.println(x);
        n_41_1 n = new n_41_1();
        n.Insert(1);
        System.out.println(n.GetMedian());
        n.Insert(4);
        System.out.println(n.GetMedian());
        n.Insert(5);
        System.out.println(n.GetMedian());
        n.Insert(6);
        System.out.println(n.GetMedian());
        n.Insert(9);
        System.out.println(n.GetMedian());
        n.Insert(2);
        System.out.println(n.GetMedian());

    }

    /**
     * 数据个数
     */
    int count=0;
    /**
     * 大顶堆，存储左边的元素
     */
    Queue<Integer> left = new PriorityQueue<Integer>(((o1, o2) -> o2-o1));
    /**
     * 小顶堆，存储右边的元素，且右边的元素大于left中所有元素
     */
    Queue<Integer> right = new PriorityQueue<Integer>();

    /**
     * 也可以把count++放在最开头，把if-else中的内容反过来
     * @param num
     */
    public void Insert(Integer num) {
        //偶数个(即第奇数个)，需要放到right中，但是要放的数必须是大于left中的，故要这么处理：
        if (count%2==0){
            left.offer(num);
            // right中即存放left中最大的值了
            right.offer(left.poll());
        }else {
            //同理哦
            right.offer(num);
            left.offer(right.poll());
        }
        count++;
    }

    public Double GetMedian() {
        if (count%2==0){
            return (left.peek()+right.peek())/2.0;
        }else {
            return (double)right.peek();
        }
    }
}
